<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>第7章 测度和度量</title>
<link rel="stylesheet" href="https://cdn.bootcss.com/highlight.js/9.12.0/styles/default.min.css">
<script src="https://cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<style>p{line-height: 28px} blockquote{margin: 20px 0px;background: #dddddd}</style>
</head>
<body>
<blockquote style="font-size: 2em">本译文仅提取精华，原文请参考<a href=""></a></blockquote>
<h1>Chap-7 Measure and Metric</h1>
<h2>Centrality Measure</h2>
<p>中心性测量方法用于研究网络中顶点的重要性或中心性。</p>
<h3>7.1 Degree Centrality</h3>
<p>度中心性指的是使用顶点的度（degree）来衡量的中心性。对于有向图来说，顶点包含出度和入度，它们都是有用的测量值，在不同的场合有各自的应用。</p>

<p>度中心性虽然很简单，但是有一定启发性。例如，对于社交网络而言，假设拥有更多联系人的个体更有影响力、能获取到更多的信息、更加具备威望还是比较合理的。一个非社交网络的例子便是使用引用数来评估科学论文。论文的引用数就是论文在citation netwrok中的入度。引用数是衡量论文是否具有影响力的天然指标，被广泛用于评价论文的影响力。</p>

<h3>7.2 Eigenvector Centrality</h3>
<p>特征向量中心性基于这样一种假设：近朱者赤，近墨者黑。也就是说，通过你朋友的中心性可以计算出你的中心性。这种想法可以说是非常自然和直观的。</p>

<p>我们从数学的角度来解读该假设。我们先考虑<font size=5 color=red>无向图</font>的情况。设$x_i$为顶点$i$的特征向量中心性，那么按照假设，$x_i \sim \sum_j A_{ij}x_j$. 这里不能取等号，因为如果 $x_i = \sum_j A_{ij}x_j$，则 $ x = Ax $. 但是一般来说，$A$ 未必包含特征根 $1$，这将导致上式无解。其中 $A$ 为图的邻接矩阵，$x$ 为中心性特征向量。</p>

<p>那么我们如何求解满足条件的 $x$ 呢？由于 $ x \sim Ax $, 我们不妨假设 $ kx = Ax,\ k > 0 $. 这说明 $x$ 是 $A$ 的一个特征向量，因此，求解 $x$ 的问题就转化为求 $A$ 的特征向量的问题。但是由于我们不知道 $k$ 具体是多少，所以我们无法直接通过求解该线性方程得到 $x$. 事实上，$A$ 所有非零特征根所对应的特征向量都可以作为 $x$ 的候选向量，只要其在实数域且满足非负性条件。</p>

<blockquote><font size=5>我们断言： $x$ 总是可以取成 $A$ 最大特征值对应的特征向量，并且总是可以通过幂法求取。</font></blockquote>

<p>1. 我们先说明为什么 $A$ 最大特征值对应的特征向量总是可以通过幂法求取。一般来说，只要网络中的顶点不都是孤立点，那么 $A$ 就是半正定矩阵，所以其所有特征向量很可能可以构成欧氏空间的一组基，满足了幂法的使用条件。<br>
2. 半正定矩阵最大特征值很可能是正的，这满足了我们对于 $k > 0$ 的约束。<br>
3. 首先，半正定矩阵的特征向量一定是实值的。其次，由 <a href="https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem">Perron–Frobenius theorem</a> 可知，存在 $A$ 最大特征根对应的特征向量，其所有分量非负。满足了我们对于 $x$ 是非负实向量的约束。其实这一点我们也可以从幂法的求解过程看出来，由于 $A$ 是非负的，所以如果幂法的初始 $x_0$ 取成非负的，那么每一步运算产生的 $ x_t $ 都是非负的，因而最终求得的 $x = \mathop{\rm lim}\limits_{t\rightarrow\infty}x_t $ 是非负的。
</p>

<p>有些时候，我们需要对中心性特征向量 $x$ 进行归一化，常见的做法是令 $ x = \dfrac{nx}{\Vert x \Vert} $, $n$是网络顶点的数目。这样所有顶点的平均特征向量中心性就不会随着网络大小的变化而变化。</p>

<p>由上面的讨论，不难看出特征向量中心性具有这样的性质：对于某个顶点而言，邻接顶点的数量越多、邻接顶点越重要，其中心性越强。对于社交网络的场景，一个人如果认识很多人或认识一些牛逼的人，那么他也应该是牛逼的。</p>

<p>请注意，上面的讨论都是针对<font size=5 color=red>无向图</font>进行的，因为无向图的邻接矩阵是对称矩阵。但是对于有向图来说，情况就有所不同了。有向图的邻接矩阵一般来说不是对称的，因而在使用特征向量中心性的时候会遇到一些困难，主要概括如下：</p>

<p>
1. 特征向量中心性定义的模糊性。不对称矩阵的左特征向量和右特征向量未必是相同的，所以我们在定义特征向量中心性的时候就遇到了困难，到底是使用出边（outgoing edge）计算左特征向量，还是使用入边（incoming edge）计算右特征向量？绝大多数情况下，如citation network, WWW, 我们都是使用右特征向量。但是不排除使用左特征向量的可能。<br>
2. 由于 $A$ 可能不是对称阵，所以难以保证有向图的 $ N $ 维的邻接矩阵恰好有 $N$ 个相互独立的特征向量，所以幂法不总是可用。<br>
3. 邻接矩阵的不对称性还可能导致极端的奇异性。 $A$ 的所有特征根可能都是0（例如 $A$ 是严格上/下三角矩阵），因而不可能有 $ x \sim Ax $, 除非 $x = 0$. 如果 $x = 0$, 特征向量中心性也失去了意义；而如果 $x \ne 0$, 特征向量中心性的假设条件就得不到满足。<br>
我们看个例子：
</p>
<img src="./pics/eigencen.png" alt="">
<p>可以看到该graph对应的邻接矩阵
$$ A = \begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0     
\end{bmatrix} $$
这很明显是一个上三角矩阵，顶点1由于没有入度，所以中心性为0，并且0还沿着PATH传递到了所有的顶点，导致所有顶点的中心性都为0。这种现象导致特征向量中心性无法用于acylic network（如citation network），因为此时所有顶点的中心性都为0.
</p>
<p>
当然除了严格上/下三角矩阵以外，还有许多矩阵的所有特征值都是0. 例如，很容易证明，幂零矩阵的所有特征值都是0（反过来未必成立）。严格上/下三角矩阵是恰好是幂零矩阵的特例，还有其他不是那么显然的幂零矩阵，例如：
$$ A = \begin{bmatrix}
0 & 0 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0   
\end{bmatrix} $$
一个问题：邻接矩阵可能出现全非正的特征值么？
</p>
<p>当然，我们还可以从图论的角度来看有向图应用特征向量中心性的困难。可以证明，只有处于拥有两个及以上顶点的强连通分支中的，或者由这种强连通分支引出的顶点才能具有非零的特征向量中心性。然而许多情况下，我们希望具有高入度的顶点，即便其满足上述两个条件，也能够拥有高的中心性。尤其是在无环网络中，例如citation network，没有任何一个强连通分支包含两个及以上的顶点，标准的特征向量中心性将导致网络中所有顶点的中心性都是0.
</p>

<p>最后，我们再稍微探讨一下如何修正特征向量中心性使其能够适用于特殊的有向图。我们知道，有向图邻接矩阵的全零特征值造成这些困难的最主要原因。因此，我们必须想办法让邻接矩阵 $A$ 出现正的特征值，这样才可能继续使用特征向量中心性那一套。在矩阵分析中，对于这种情况，我们最常用的处理方法就是给矩阵加上一个 $\lambda I, \lambda > 0$. 也就是说，现在方程变成了 $ kx = (A + \lambda I)x $. 从Graph的角度来看，这个方程的含义是给每个顶点强行加一条指向自己的环边，该环边也能对中心性做出贡献。也就是说该方法保证了所有顶点都有入度，避免了顶点由于没有入度而中心性为0的情况。</p>

<p>当然，还有其他refine特征向量中心性的方法，如KATZ CENTRALITY.</p>

<h3>7.3 KATZ CENTRALITY</h3>

<p>从另一个角度来看，特征向量中心性在部分有向图中失效的原因在于方程 $ kx = Ax $ 只有零解。这意味着 $ kI - A $ 是可逆函数。如果我们想要获得非零解，那么一种可能的做法就是令方程 $ (kI - A)x = 0 $ 的右边为某个非零向量，也就是令 $ (kI - A)x = b $. 这就是KATZ中心性的出发点。</p>

<p>在KATZ中心性中， $x$ 满足方程 $(I - \alpha A)x = \beta$, $\beta$ 一般取全1向量。 也就是说， $x = \alpha Ax + 1$. 从graph的角度来看，所有顶点都额外获得了1中心性，从而所有顶点的中心性 $ x_i > 1 $，即便其入度可能为0, 每个顶点也都将从incoming edge中获益。</p> 

<p>下面我们考虑一下KATZ中心性方程 $(I - \alpha A)x = 1$ 的求解。和特征向量中心性不同，KATZ中心性方程中的未知参数 $\alpha$ 和 $A$ 没有必然联系，它可以取实数域上的任何值。因此，我们有必要讨论一下 $x$ 和 $\alpha$ 的取值之间的关系。</p>

<p>我们定义函数 $h(\alpha) = det(I - \alpha A)$. 我们当然希望选取 $\alpha$ 使得 $h(\alpha) \ne 0$, 这样我们可以直接解得 $x = (I - \alpha A)^{-1} 1$. 然而，什么时候 $h(\alpha) = 0$ 呢？恰恰是当 $\alpha^{-1}$ 成为 $A$ 的特征值的时候。然而， $A$ 的特征值是有限的， $\alpha$ 可能的取值是无限的，我们该如何选择？由于我们不知道 $A$ 的特征值的情况，所以我们无法获取 $h(\alpha)$ 的具体图像；但是一些大致的趋势还是可以看出来的：</p>
<p>1. 当 $\alpha \rightarrow 0$ 时，邻居的影响趋于0. 所有顶点的中心性都将等于1. <br>
2. 当 $\alpha \rightarrow \infty$ 时。一般来说，在 $\alpha > \dfrac{1}{k}$, （ $k$ 是 $A$ 的特征值，可能正也可能负，但是一定要使得 $\dfrac{1}{k}$ 最大） 之后， $x$ 就逐渐变成全负向量了，此时方程不再存在 $x = (I - \alpha A)^{-1} 1$ 非负解。当然，如果全部分量都是非正的，那么某种意义上，我们也可以使用这样的解作为中心性向量，因为只是差了一个符号而已。<br>
另一方面，单纯从 $x = \alpha Ax + 1$ 的形式来看，随着 $ \alpha \rightarrow \infty $, $x$ 要么就是取值 $\infty$, 要么就是不断逼近于 $0$ . 这两者是对偶的——如果我们使用迭代法去求 $x$, 也就是令 $ x_t = \alpha Ax_{t-1} + 1 $, 那么毫无疑问， $x$ 最终会收敛到 $\infty$; 但是如果我们直接使用求逆矩阵的方法求解 $x$, 那么毫无疑问 $x \rightarrow 0$. （有一点哲学上的观点是，虽然此时迭代法在当前空间不收敛，但是在对偶空间中可能是收敛的，所以研究一些发散的数列也是有其理论意义的，这是我从动力系统的学习中感受到的数学之美。）<br>
3. 当 $\alpha$ 从 0 开始增长的时候，中心性也会随之增长（中心性向量的范数），但是当 $\alpha$ 增长到 $A$ 的倒特征根附近的时候，中心性向量会急剧发散（类似冲激函数），这时候， $ (I-\alpha A)^{-1} $ 也非常不稳定，而 $det(I-\alpha A)$ 将 pass through 0. 我们这里讲收敛和发散，主要是指其能不能表达成收敛/发散的级数，也就是指采用迭代法能不能收敛。<br>
4. 在 $A$ 的倒特征根附近，解的性质很奇特。我们考虑 $ k_1,\ k_2 $, 其中 $k_1$ 是最大特征根， $k_2$ 是最小正特征根。我们可以发现，在 $\dfrac{1}{k_1}$ 附近，解向量在归一化之后及其接近 $A$ 中与 $k_1$ 对应的特征向量，另一方面，当 $ \alpha\rightarrow\infty $, 解向量在归一化之后却和 $A$ 的特征向量想去甚远。这真的是很有趣的性质，我们观察一下方程形式 $x = \alpha Ax + 1$, 当 $\alpha\rightarrow\infty$, 讲道理我们对邻居的影响已经调到无穷大了，这时候，这时候解应该非常接近特征向量才对；然而，没想到，在 $\dfrac{1}{k_1}$ 附近的时候，解向量在特征向量上的权重才是最大的，在常数向量 $ 1 $ 上的权重才是最小的！
</p>

<p>接下来，我们讨论一下 $\alpha$ 的取值。首先，由上述第2点，$\alpha$ 不宜过大，否则方程 $x = (I - \alpha A)^{-1} 1$ 不存在非负解。由第1点，$\alpha$ 不宜过小，否则邻居节点之间没有相互影响的。但是，如果 $\alpha$ 取值在 $A$ 的两个正的倒特征根之间的话（如果存在两个以上正的倒特征根的话），那么 $x = (I - \alpha A)^{-1} 1$ 是否具有非负解就难以判定了，就算是有非负解，我们也难以保证解的所有分量都是大于1的。<br>

如果 $A$ 的最大特征值 $k_1$ 是正的，那么我们一般希望在 $(0, \dfrac{1}{k_1})$ 之间取 $\alpha$ 的值，因为在这个区间内，我们可以保证 $x = (I - \alpha A)^{-1} 1$ 的解所有分量都是大于1的，符合我们的期望；而且，在这个区间内，中心性向量的范数可以取到 $[1,\infty)$ 之间的所有值，非常灵活。有些研究者偏向于取接近 $\dfrac{1}{k_1}$, 因为这时候的解向量非常接近 $A$ 的特征向量，近似保证了 $ x \sim Ax $, 符合我们的直观。并且此时 $x$ 所有的分量都是正的（ $ >> 1$, 因为这时 $\alpha\sim\dfrac{1}{k_1}$. ）。归一化之后，不在强连通分支中的，或者不是由强连通分支引出的顶点，其中心性 $x_i$ 会较小，有些情况下趋于0，符合我们的直观。<br>

如果 $A$ 的最大特征值是非正的，那么很有可能随着 $\alpha$ 的增长，我们只能在一个有限的区间内保证 $x = (I - \alpha A)^{-1} 1$ 存在非负解，但是无法保证解的所有分量都是大于1的，而且中心性还会随着 $\alpha$ 的增大而缩小；也就是说这种时候 KATZ中心性已经玩完了，我们是得不到我们想要的解的，那么这种情况：<font color=red>$A$ 的最大特征值是非正的</font> 会不会出现呢？有哪些满足条件的 $A$, 这时候的网络具有什么样的性质？<font color=red>研究KATZ中心性的适用情况也是一个重要的问题</font>.
</p>

<p>说到了这里，不提一下函数 $V_A(\alpha) = (I - \alpha A)^{-1} 1$ 就有点不够意思了。函数 $V_A(\alpha)$ 当 $\alpha$ 取值在 $\dfrac{1}{k}$ （ $k$ 是 $A$ 的任一特征值 ）附近时，性质非常的奇异。由于直接观察 $V_A(\alpha)$ 的性质比较困难，我们可以从一些侧面，例如 $\Vert V_A(\alpha) \Vert$ 以及 $ \dfrac{1}{n}\sum_{i=1}^n sgn(V_A(\alpha)_i) $ 来研究 $V_A(\alpha)$ 的性质（这些都是一维指标，易于作图）；另一方面，对迭代法收敛性的研究也许也可以提供某些线索。目前由于缺少相应的数学工具， $V_A(\alpha)$ 留待后面研究。不知道能不能通过逆矩阵公式把 $V_A(\alpha)$ 展开。</p>

<p>接下来我们考虑一下方程 $x = \alpha Ax + 1$ 的求解问题。常见的解法由Gauss消去法、LU分解法、Jacobi迭代法和Gauss-Seidel迭代法。在我们的问题中，由于 $A$ 的对角线一定为0，所以方程 $x = \alpha Ax + 1$ 天然就形成了Jacobi迭代式。那么对于我们的问题，该迭代过程收敛的条件是什么？依据Jacobi迭代法的收敛条件，我们可以得到此时的收敛条件是 $ \rho(\alpha A) < 1 $. 假设 $k$ 是 $A$ 中所有特征值中<font color=red>绝对值最大的</font>，也就是 $|k|$ 是 $A$ 的谱半径。那么 $ \rho(\alpha A) < 1 $ 就等价于使得 $ \alpha |k| < 1 $, 即 $\alpha < \dfrac{1}{|k|}$. 也就是说，迭代法不能乱用的，必须保证 $\alpha$ 满足 $\alpha < \dfrac{1}{|k|}$ 这个条件才行。另外，迭代初始值的选取也是很重要的，选的太差可能使迭代不收敛或者收敛的很慢。对于我们的问题来说，可以令 $x^{(0)} = 0$, 一般来说，估计初始值的时候需要综合考虑网络的细节和 $\alpha$ 的取值。一般对于大型网络而言，我们不希望直接对矩阵求逆或是使用LU分解，因为它们都是 $O(n^3)$ 的计算复杂度。我们倾向于使用迭代法，Jacobi迭代的复杂度是 $O(rn^2)$, 其中 $r$ 是迭代的次数。如果初始值选的好， $r$ 会很小，迭代很快就会收敛，这样整体的计算量就比求逆类方法小得多了。所以对于大型网络，我们偏向于使用迭代法求解。</p>

<p>KATZ中心性可以看作是特征向量中心性的一个增强版本，它可以得到和特征向量中心性非常近似的解，同时也避免了特征向量中心性的一些问题。但是KATZ是否对于所有邻接矩阵 $A$ 都能适用还有待进一步探索，但是其适用范围确实比特征向量中心性大得多。当然，KATZ中心性也可以用于无向图，不过应该和特征向量中心性差不多。</p>

<p>KATZ中心性的一种扩展是，让每个顶点加上的常数项不同，也就是 $ x_i = \alpha \sum_j A_{ij}x_j + \beta_i $. 这样一种扩展在社交网络中挺有用的，因为有些时候，我们也需要按照用户的一些本身的特性如年龄、收入、职位等等来为其赋予其不同的中心性，而不仅仅依靠用户之间的互联情况。这时候，通过引入不同的 $\beta_i$ 就可以解决这个问题。不过这个方法有个问题，那就是无法实现增量改变用户的中心性，什么意思呢？当一个用户的资料发生改变时，也就是 $\beta_i$ 改变时，整个网络的中心性 $x = (I-\alpha A)^{-1}\beta$ 都需要重新计算。当然，我们可以预存 $ (I-\alpha A)^{-1} $ 来减少计算量。如果网络中不同用户的资料改变很频繁时，这样做是有效的，因为虽然计算逆矩阵是 $O(n^3)$ 的，但是一旦计算完成，我们就一劳永逸了，求解新的 $x$ 的时候，只要做一次简单的矩阵乘法就可以了；最后平摊下来，平均每次的计算量甚至比迭代法每次的计算量还要省，也不会遇到迭代法需要选初始值这样头疼的问题——不好的初始值选择会让迭代法的迭代次数增多甚至最后不收敛，好的初始值一般应该是比较接近真实解的，因此有时候，我们需要先针对真实解先做一次估计。</p>

<p></p>


</body>
<script>hljs.initHighlightingOnLoad();</script>
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script src="https://cdn.bootcss.com/mathjax/2.7.3/MathJax.js?config=TeX-AMS_HTML"></script>
</html>